package week02

// 50. Pow(x, n)
// https://leetcode-cn.com/problems/powx-n/

// x * pow(x, n-1) 这个不用区分奇偶，但是性能比较差，且栈太深，容易爆炸 时间复杂度：O(n)
// pow(x, n / 2)  注意：奇数情况下要多乘以一次 x	时间复杂度：O(logN)

func myPow(x float64, n int) float64 {
	return pow(x, int64(n))
}

func pow(x float64, n int64) float64 {
	if n == 0 {
		return 1
	}
	if n < 0 {
		return 1 / pow(x, -n)
	}
	y := pow(x, n / 2)
	if n % 2 == 0 {
		return y * y
	}
	return x * y * y
}
